COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00006 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A93.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 27, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent {\bf Reflexive Transitive Closures}

Say $\sigma$ is a {\it reflexive transitive extension} (RTE) of $\rho$ if
$\delta\subset\sigma$ (reflexive), $\sigma\circ\sigma\subset\sigma$
(transitive), $\rho\subset\sigma$ (extension).  The {\it reflexive
transitive closure} (RTC) of $\rho$, called $\rho↑*$, is the least reflexive
transitive extension of $\rho$; that is, $\rho↑*$ is a RTE of $\rho$, 
and if $\sigma$ is a RTE of $\rho$, $\rho↑*\subset\sigma$.  Let $S$ be any 
collection of RTEs of $\rho$; then $\bigcap S$ is an RTE of $\rho$ (Prove it).
Let $T$ be the set of all RTEs of $\rho$, and $\tau = \bigcap T$.
Then $\tau$ is an RTE of $\rho$, so $\tau\in T$.  If $\tau'$ is any RTE of
$\rho$, $\tau = \bigcap T \subset\tau'$.  Therefore $\tau$ meets the
definition of $\rho↑*$.  If there were two RTCs of $\rho$, each wuld be a
subset of the other, so they would be equal.  Any relation therefore has a
unique RTC that is the intersecton of all the RTEs.

The pattern of the previous paragraph is frequently used in mathematics
to characterize the least object that has some desired proper.  The intersection
of all the objects that have the property is less than or equal to each of
them, and if the property is preserved by intersection, the intersection itself
has the property.
\smallskip
\noindent Because $\rho\subset\rho↑*$, $\rho↑{-1}\subset (\rho↑*)↑{-1}$.

\noindent Because $\delta\subset\rho↑*$, $\delta =\delta↑{-1}\subset (\rho↑*)↑{-1}$.

\noindent Because $\rho↑*\circ\rho↑*\subset\rho↑*$, $(\rho↑*)↑{-1}\circ (
\rho↑*)↑{-1}
\subset (\rho↑*)↑{-1}$.
\smallskip
Therefore $(\rho↑*)↑{-1}$ is an RTE of $\rho↑{-1}$, and $(\rho↑{-1})↑*\subset
(\rho↑*)↑{-1}$.

Substituting $\rho↑{-1}$ for $\rho$, $\rho↑*\subset ((\rho↑{-1})↑*)↑{-1}$.
Taking the converse of both sides, $(\rho↑*)↑{-1}\subset (\rho↑{-1})↑*$.
By mutual inclusion $(\rho↑{-1})↑* = (\rho↑*)↑{-1}$.
\bye